Most computer systems include a processor and a memory system. The speed at which the processor can decode and execute instructions to process data has for some time exceeded the speed at which instructions and operands can be transferred from the main memory of the memory system to the processor. In an attempt to reduce the problems caused by a mismatch in speed, many computer systems also include a cache memory between the processor and the main memory.
A cache memory is a small, high-speed buffer memory which is used to temporarily hold a copy of those portions of the contents of main memory which are likely to be used in the near future by the processor. Typically, when the processor requires an instruction, the instruction is fetched from the cache memory or from the main memory via an instruction bus. The main purpose of a cache memory is to shorten the time necessary to provide the processor with required data or instructions. The information located in cache memory may be accessed in much less time than that located in main memory. Thus, a processor with a cache memory needs to spend far less time waiting for instruction and operands to be fetched and/or stored. For example, in typical large, high-speed computers, main memory can be accessed in 300 to 600 nanoseconds and cache memory in 20 to 40 nanoseconds.
The desired objective of a cache memory scheme is to maximize the probability of finding a main memory reference's information in the cache, to minimize the time required to access information that is needed by the processor (access time), and to minimize the delay due to a cache miss.
All of these objectives must be accomplished under cost constraints and in view of the interrelationship between the parameters, for example, the trade-off between hit ratio and access time.
The probability of finding the needed information in the cache memory is proportional to its size which of course depends on numerous factors such as cost, physical size, and access time.
More recently, cache memories have been coupled with instruction prefetch circuits for providing the storage of future processor instruction requests in the cache before the processor actually invokes the request. When instructions are prefetched from a main memory and written to a cache memory, those prefetched instructions may overwrite previously written instructions stored within the cache. This overwriting of previously written instructions with prefetched instructions is in effect replacing an historical portion of the cache with a predictive portion. In a predictive caching scheme where instructions are prefetched before they are requested by a processor, they are generally prefetched in sequential order. When an unconditional branch instruction is encountered, a prefetch unit usually follows the branch path and sequential instructions following the branch instruction are subsequently prefetched. When a conditional branch instruction is encountered, the prefetch unit having no information about the outcome of the branch condition will generally be programmed to prefetch instructions following the conditional branch instruction along the straight-through path, therefore not prefetching along the branch path. This, of course, is entirely a matter of design choice. It might be preferable in some instances to prefetch instructions along the branch path as the default on a conditional branch instruction.
In some instruction prefetching schemes, where the default condition is to take the straight-through path in the instance that a conditional branch instruction is encountered, the compiler orders the instructions in favour of the prefetch circuit's default condition which is the straight-through path; in essence, the instructions are ordered such that the likelihood of a conditional branch path being taken is less than 50 percent and the likelihood that the straight-through path is taken is greater than 50 percent.
Other schemes are known which attempt to predict the outcome of a conditional branch instruction before it is encountered so that the prefetch unit may make a decision regarding which path to take and therefore, which instructions to prefetch. Many of these schemes are less than ideal since decisions regarding which prefetch path to take are made based on the likelihood or probability of an expected result or outcome.
It is an object of the invention to provide an improved method of providing and maintaining a cache memory with instructions.